package graph;

import java.util.*;

/**
 * 系统堆实现的Dijkstra算法优化版
 *
 * @author lcw
 * @date 2023/12/11
 */
public class DijkstraGoodByNormalHeap {
    /**
     * 获取源点到图中任意点的最短距离
     *
     * @param node 源点
     */
    public static Map<Node<Integer>, Integer> dijkstra(Node<Integer> node) {
        Map<Node<Integer>, Integer> distMap = new HashMap<>();
        PriorityQueue<NodeWithWeight<Integer>> q = new PriorityQueue<>();
        distMap.put(node, 0);
        q.offer(new NodeWithWeight<>(node, 0));
        Set<Node<Integer>> freezeNodes = new HashSet<>();

        while (!q.isEmpty()) {
            NodeWithWeight<Integer> nd = q.poll();
            if (freezeNodes.contains(nd.node)) {
                continue;
            }
            freezeNodes.add(nd.node);

            for (Edge<Integer> nextEdge : nd.node.nextEdges) {
                int dist = distMap.get(nd.node) + nextEdge.weight;
                if (dist < distMap.getOrDefault(nextEdge.to, Integer.MAX_VALUE)) {
                    // 普通的优先队列，不能做更新操作，只能添加一个点与权值组成的二元组，最坏的情况每个边都会添加一个
                    // 导致算法时间复杂度从O(nlogn)变为O(mlogn)，其中m为边数
                    q.offer(new NodeWithWeight<>(nextEdge.to, dist));
                    distMap.put(nextEdge.to, dist);
                }
            }
        }

        return distMap;
    }

    private static final class NodeWithWeight<T> implements Comparable<NodeWithWeight<T>> {
        Node<T> node;
        Integer weight;

        public NodeWithWeight(Node<T> node, Integer weight) {
            this.node = node;
            this.weight = weight;
        }

        @Override
        public int compareTo(NodeWithWeight o) {
            return this.weight != o.weight ? this.weight - o.weight : this.node.hashCode() - o.node.hashCode();
        }
    }
}
